package history.hot100;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// 46. 全排列
// https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-by-powcai-2/
public class LeetCode_46 {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        int []visited = new int[nums.length];
        Arrays.fill(visited, 0);;
        backtracking(nums, visited, new ArrayList());
        return result;
    }

    private void backtracking(int []nums,int [] visited, ArrayList temp) {
        int length = nums.length;
        if (temp.size() == length) {
            result.add(new ArrayList<>(temp));
            return;
        }

        for (int i = 0; i < length; i++) {
            if (visited[i]==1) continue;
            visited[i] = 1;
            temp.add(nums[i]);
            backtracking(nums, visited, temp);
            visited[i]=0;
            temp.remove(temp.size()-1);
        }
    }
}
